单链表反转（逆置） |
您所在的位置：网站首页 › 链表逆序 非递归java › 单链表反转（逆置） |
单链表反转（逆置）
|
链表逆置就是把最后一个数据提到最前面，倒数第二个放到第二个……依次类推，直到第一个到最后一个。 由于链表没有下标，所以不能借助下标来实行数据的逆置，要靠空间的转移来完成链表的逆置，这里采用没有头节点的链表来实现逆置。 第一种——头插法 算法思想：逆置链表，初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。 #include #include typedef struct List{ int data; struct List* next; }LIST; //表的初始化，不带头节点， LIST* CreatSlist() { LIST* head=NULL; for(int i=5;i>=1;i--) { LIST* newhead=(LIST *)malloc(sizeof(LIST)); newhead->data=i; newhead->next=head; head=newhead; } return head; } //打印输出 void print(LIST* P) { while(P!=NULL) { printf("%d ",P->data); P=P->next; } printf("\n"); return; } //单链表反转（头插法） LIST* reverse(LIST* head) { LIST *temp=NULL,*Phead=NULL; while(head!=NULL) { temp=head; head=head->next; temp->next=Phead; Phead=temp; } return Phead; } int main () { printf("原来的链表的数据:\n"); LIST* P=CreatSlist(); print(P); printf("反转后链表的数据:\n"); LIST* head=reverse(P); print(head); return 0; }结果如下：
第二种——递归 算法思想：先假定有一个函数，可以将以head为头结点的单链表逆序，并返回新的头结点。利用这个函数对问题进行求解：将链表分为当前表头结点和其余部分，递归的过程就是，先将表头结点从链表中拆出来，然后对其余部分进行逆序，最后将当前的表头结点链接到逆序链表的尾部。递归的终止条件就是链表只剩一个节点时，直接返回这个节点 #include #include typedef struct List{ int data; struct List* next; }LIST; //表的初始化，不带头节点， LIST* CreatSlist() { LIST* head=NULL; for(int i=5;i>=1;i--) { LIST* newhead=(LIST *)malloc(sizeof(LIST)); newhead->data=i; newhead->next=head; head=newhead; } return head; } //打印输出 void print(LIST* P) { while(P!=NULL) { printf("%d ",P->data); P=P->next; } printf("\n"); return; } //单链表反转（递归法） LIST* reverse(LIST* head) { if(head==NULL||head->next==NULL) return head; LIST *new_head=reverse(head->next); head->next->next=head; head->next=NULL; return new_head; } int main () { printf("原来的链表的数据:\n"); LIST* P=CreatSlist(); print(P); printf("反转后链表的数据:\n"); LIST* head=reverse(P); print(head); return 0; }结果如下：
第三种——迭代法 算法思想：链表迭代逆置的时候需要借助三个指针，这里我们把三个指针定义为p1,p2,p3.然后让这三个指针迭代更新。 #include #include typedef struct List{ int data; struct List* next; }LIST; //表的初始化，不带头节点， LIST* CreatSlist() { LIST* head=NULL; for(int i=5;i>=1;i--) { LIST* newhead=(LIST *)malloc(sizeof(LIST)); newhead->data=i; newhead->next=head; head=newhead; } return head; } //打印输出 void print(LIST* P) { while(P!=NULL) { printf("%d ",P->data); P=P->next; } printf("\n"); return; } //单链表反转(迭代反转) LIST* reverse(LIST* head) { LIST *p1=NULL,*p2=NULL,*p3=NULL; p1=head; p2=p1->next; while(p2!=NULL) { p3=p2->next; p2->next=p1; p1=p2; p2=p3; } head->next=NULL; head=p1; p1=NULL; return head; } int main () { printf("原来的链表的数据:\n"); LIST* P=CreatSlist(); print(P); printf("反转后链表的数据:\n"); LIST* head=reverse(P); print(head); return 0; }结果如下:
第四种——就地逆置 算法思想：就地逆置法和头插法的实现思想类似，唯一的区别在于，头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。在原链表的基础上做修改，需要额外借助 2 个指针（假设分别为 p和 q）。 #include #include typedef struct List{ int data; struct List* next; }LIST; //表的初始化，不带头节点， LIST* CreatSlist() { LIST* head=NULL; for(int i=5;i>=1;i--) { LIST* newhead=(LIST *)malloc(sizeof(LIST)); newhead->data=i; newhead->next=head; head=newhead; } return head; } //打印输出 void print(LIST* P) { while(P!=NULL) { printf("%d ",P->data); P=P->next; } printf("\n"); return; } //单链表反转（就地逆置） LIST* reverse(LIST* head) { LIST *p=NULL,*q=NULL; p=head; q=head->next; while(q!=NULL) { p->next=q->next; q->next=head;; head=q; q=p->next; } p=NULL; return head; } int main () { printf("原来的链表的数据:\n"); LIST* P=CreatSlist(); print(P); printf("反转后链表的数据:\n"); LIST* head=reverse(P); print(head); return 0; }结果如下：
|
【本文地址】